home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 15644 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  8.8 KB
  1. Path: solon.com!not-for-mail
  2. From: kjm@sbphy.physics.ucsb.edu ( Kevin Miller)
  3. Newsgroups: comp.lang.c,comp.lang.c.moderated
  4. Subject: Re: 8 Queens prog help
  5. Date: 20 Apr 1996 13:34:23 -0500
  6. Organization: University of California, Santa Barbara
  7. Sender: clc@solutions.solon.com
  8. Approved: clc@solutions.solon.com
  9. Message-ID: <4lbanf$ljv@solutions.solon.com>
  10. References: <4l87ud$73u@solutions.solon.com>
  11. NNTP-Posting-Host: solutions.solon.com
  12.  
  13. Mike Mitchell <72724.2067@CompuServe.COM> writes:
  14.  
  15. >Need some C help this week.  I'm currently working on a program 
  16. >called "Eight Queens".  Basically, I have to place 8 queen chess 
  17. >pieces on an 8x8 chess board without them checking one another.  
  18.  
  19. >The instructer wants us to use a "backtracking algorithm" (i.e. a 
  20. >tree structure) to accomplish this.  My thoughts thus far are to 
  21. >place my first queen randomly and mark that space with a 'Q' 
  22. >character and then mark off all the squares in its legal paths 
  23. >(all adjacent squares vertical, horizontal, and diagonal to the 
  24. >ends of the board) with an 'X' character.  Board is initialized 
  25. >to Nulls.
  26.  
  27. >When the next queen piece is placed I will check to see if 
  28. >another queen is in one of its paths.  If there isn't I will 
  29. >place the piece and mark off its paths otherwise I will return 
  30. >the square to NULL and move to the next NULL square.
  31.  
  32. >Am I approaching this the right way or should I be handling this 
  33. >another way?  Can someone explain how a tree structure 
  34. >accomplishes this?
  35.  
  36. >We did a similar problem in class using the knight piece and its 
  37. >legal moves.  Well, needless to say the number of legal moves a 
  38. >queen can make, make this problem a little more difficult. 
  39.  
  40. If anything, the greater number of moves that the queen can make should 
  41. make this problem *easier* to do than the corresponding problem for the 
  42. knight.  This is assuming, of course, that your algorithm for solving 
  43. the knight problem was actually exhaustive.  The number of ways of 
  44. placing eight knights on a chessboard without any of them attacking 
  45. each other is large enough that a non-exhaustive algorithm, by which 
  46. I mean one that overlooks some possible solutions, would still have 
  47. a good chance of finding at least one solution.  (Hell, putting eight 
  48. knights all on the same row would work.)  But an algorithm that would 
  49. correctly find *all* solutions to the "eight knights" problem should 
  50. be quite easy to modify for the "eight queens" problem.  
  51.  
  52. I am not sure why your instructor wants you to use a tree, if that is 
  53. really what he meant.  Storing the whole search tree would use up an 
  54. awfully wasteful amount of memory, and serve no purpose.  Possibly he 
  55. means that you should have stored, at any one time, one path along 
  56. the search tree.  (But that would not really need to be stored in 
  57. a tree-like structure; it would just be a simple array.)  
  58.  
  59. What I would do is first invent a way of numbering the squares with a 
  60. single integer.  For example, let H be the horizontal coordinate and 
  61. let V be the vertical coordinate, where both H and V take values 
  62. between 0 and 7 inclusive, and let the number associated with a square 
  63. be N = 8 * V + H.  The squares then have numbers ranging from 0 to 63.  
  64.  
  65. Then I would create an array of dimension 8 that would hold the positions 
  66. of each of the eight queens.  Initialize this array to all zeros.  
  67. This is not a legal position, in that it has all of the queens on top 
  68. of each other in the lower left-hand corner.  But this is OK, this is 
  69. the starting point, not the solution.      
  70.  
  71. Then you need to start iterating, going from one possible solution to 
  72. another, until you get to (or go past) the last possible solution, where 
  73. all eight queens are on square 63.  
  74.  
  75. Now how do you go from one possible solution to another, in a 
  76. way that will generate all of the solutions and yet be efficient?  
  77. One (inefficient) way is what I would call the odometer method.  
  78. You increment the last element in the array.  If that causes it to 
  79. exceed 63, then you set it to zero and increment the element just 
  80. before it.  If incrementing *that* element causes *it* to exceed 
  81. 63, then set that element to zero also and then increment the element 
  82. preceding that one.  Repeat this in an obvious way until you get 
  83. an element that does not exceed 63 after it is incremented.  The 
  84. result is the next possible solution for you to examine.  You must 
  85. then check to see if it meets all of the requirements.  If so, print 
  86. it out.  If not, go on to the next possible solution.  
  87.  
  88. The odometer method will probably not give you an answer in the time 
  89. that you will have available on your computer.  The entire search 
  90. would require 64-raised-to-the-8'th-power iterations, which 
  91. is roughly 2.8e+14, in the usual floating-point notation.  
  92.  
  93. So here is a much more efficient way, which I think may be what your 
  94. professor was calling a backtracking algorithm.  (Someone please correct 
  95. me if I am wrong.  I am mostly self-taught, so I don't know the names 
  96. for a lot of these things.)  Suppose you have just examined the following 
  97. configuration:  
  98.  
  99.      (0,10,25,3,4,5,6,7) 
  100.  
  101. This corresponds to this board position:  
  102.  
  103.          +-----------------+
  104.          | . . . . . . . . |
  105.          | . . . . . . . . |
  106.          | . . . . . . . . |
  107.          | . . . . . . . . |
  108.      25 >| . Q . . . . . . |
  109.          | . . . . . . . . |
  110.      10 >| . . Q . . . . . |
  111.          | Q . . Q Q Q Q Q |
  112.          +-----------------+
  113.            ^     ^ ^ ^ ^ ^ 
  114.            0     3 4 5 6 7 
  115.  
  116. If you follow the odometer algorithm, then you will end up trying all 
  117. possible alternative positions for the last queen (now on square 7), and 
  118. then you will try the next position for the queen now on square 6, and 
  119. then try all possible positions for the last queen again.  All of 
  120. this, in spite of the fact that the position will be unacceptable no 
  121. matter where you put the queens that are now on squares 6 and 7, simply 
  122. because the queens on squares 0 and 3 are attacking each other.  
  123. So what you should do is the following.  Search through the array to find 
  124. the first queen in the array whose position is unacceptable because of 
  125. one of the queens that came earlier in the array.  In this example, this 
  126. will be the queen on square 3.  Increment that array element, so the 3 
  127. becomes a 4, and then set all of the array elements after that to 0.  
  128. This will give you this configuration:  
  129.  
  130.      (0,10,25,4,0,0,0,0) 
  131.  
  132. This is the next configuration which you must examine.  It is also 
  133. unacceptable, both because the queen on square 4 is in the same row 
  134. with a queen on square 0, and also because there are actually five 
  135. queens all on the same square, namely square 0.  Nevertheless, you 
  136. have skipped over millions of pointless-to-consider configurations.  
  137. In any case, you keep repeating this process.  But there is a 
  138. complication we still haven't considered for this algorithm.  
  139. Eventually you may arrive at a configuration like the following: 
  140.  
  141.      (0,10,25,63,3,4,5,6) 
  142.  
  143. This corresponds to this board position:  
  144.  
  145.          +-----------------+
  146.      63 >| . . . . . . . Q |
  147.          | . . . . . . . . |
  148.          | . . . . . . . . |
  149.          | . . . . . . . . |
  150.      25 >| . Q . . . . . . |
  151.          | . . . . . . . . |
  152.      10 >| . . Q . . . . . |
  153.          | Q . . Q Q Q Q . |
  154.          +-----------------+
  155.            ^     ^ ^ ^ ^   
  156.            0     3 4 5 6   
  157.  
  158. Now the queens on squares 0, 10, and 25 do not attack each other, but 
  159. the queen on square 63 is on the same diagonal as the queen on square 0.  
  160. This means that we should increment the 63, and set all the elements 
  161. after it in the array equal to zero, giving us this configuration:  
  162.  
  163.      (0,10,25,64,0,0,0,0) 
  164.  
  165. But 64 is not the number of any square.  Square numbers only run 
  166. from 0 to 63.  So we set the 64 equal to zero, and increment the 
  167. preceding element, giving us this configuration:  
  168.  
  169.      (0,10,26,0,0,0,0,0) 
  170.  
  171. This is our next configuration to consider, and we continue as before.  
  172. If you ever get to the point where you are forced to increment 
  173. the first element (i.e., the element Arr[0], where Arr is the 
  174. array name) *and* incrementing it causes *it* to exceed 64, then you 
  175. have searched all posibilities, and you should stop.  For example, you 
  176. might encounter this configuration:  
  177.  
  178.      (63,63,0,0,0,0,0,0) 
  179.  
  180. The second queen is on the same square (63) as the first one, so you 
  181. should increment the second 63, and set everything after it to zero, 
  182. giving you this: 
  183.  
  184.      (63,64,0,0,0,0,0,0) 
  185.  
  186. But then the second element exceeds 63, so you set it equal to zero and 
  187. increment the element before it, giving you this:  
  188.  
  189.      (64,0,0,0,0,0,0,0) 
  190.  
  191. But now the very first element is 64, which exceeds 63, so you can stop.  
  192.  
  193. By the way, this is not really a C question.  The comments above apply 
  194. equally well, whether you are programming in C, Fortran, assembly 
  195. language, or even (gag) Cobol.  
  196.  
  197.                - Kevin Jay Miller 
  198.  ` 
  199.